Masala #0878

Jahongir ketma-ketliklarga qiziqadi. Bir kuni u ustozi bergan ketma-ketlik qaysi qonuniyat asosida ketishini aniqlash va shu ketma-ketlikning n-hadini oxirgi raqamini topish kerak edi. Jahongir qonuniyatni topdi! Qonuniyat shundan iborat ediki ketma-ketlikning dastlabki 3ta hadi beriladi. keyingi har bir had o'zidan oldingi 3ta hadning yig'indisiga teng. Endi sizning vazifangiz shu qonuniyat asosida ketma-ketlikning n-hadini topib Jahongirga yordam berishdan iborat

Birinchi qatorda probel bilan ajratilgan holda 3ta butun son a, b, c va keyingi qatorda q butun sonlari kiritiladi. Keyingi qatorda probel bilan ajratilgan holda q ta butun son probel bilan ajratilgan holda kiritiladi.   \((1 \leq a, b, c \leq 10^{18}, 0 < q \leq 1000, 1 \leq n \leq 10^{18})\) 

Chiqish faylida bitta qatorda q ta so'rov uchun ketma-ketlikning n-hadning oxirgi raqami probellar bilan ajratilgan holda chiqarilsin.